import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

/**
 * http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15648&pm=12544
 * 
 * @author smarsoll
 * 
 */
public class CopyOfFragileMirrors {

	/** Maximum time 1 in ms. */
	private static final int MAX_TIME_1 = 4400;
	private static final int MAX_TIME_2 = 9000;
	private long startTime;

	/**
	 * 
	 * @param board
	 *            {"LLLR", "RLRR", "LLLL", "RRRL"}.
	 * @return {4, 2, -1, 1}.
	 */
	public int[] destroy(String[] board) {
		startTime = System.currentTimeMillis();
		int boardSize = board.length;
		BoardW field = new BoardW(board);
		List<CellW> lstRays = new ArrayList<CopyOfFragileMirrors.CellW>();
		Collection<CellW> possibleRays = getPossibleRays(boardSize);
		while (field.nbMirrors > 0) {
			// CellW ray = getBestRay(possibleRays, field);
			List<CellW> curRays = getBestRays(possibleRays, field, 2);
			field.shootRay(curRays);
			lstRays.addAll(curRays);
		}
		// for (int i = 0; i < boardSize; i++) {
		// for (int j = 0; j < boardSize; j++) {
		// CellW ray = new CellW(-1, j);
		// BoardW aTest = new BoardW(field);
		// int nbShot = aTest.shootRay(ray);
		// if (nbShot > 0) {
		// log(" nbShot=" + nbShot);
		// field.shootRay(ray);
		// lstRays.add(ray);
		// }
		// if (field.nbMirrors == 0) {
		// break;
		// }
		// }
		// if (field.nbMirrors == 0) {
		// break;
		// }
		// }

		// translation for result
		int[] rays = new int[2 * lstRays.size()];
		int curRay = 0;
		for (CellW cellW : lstRays) {
			rays[curRay * 2] = cellW.r;
			rays[curRay * 2 + 1] = cellW.c;
			curRay++;
		}
		log("lstRays.size=" + lstRays.size() + " , time-taken=" + (System.currentTimeMillis() - startTime));
		return rays;
	}

	// private CellW getBestRay(Collection<CellW> possibleRays, BoardW field) {
	// CellW bestRay = null;
	// int bestShot = 0;
	// boolean oneFound = false;
	// for (Iterator<CellW> iterator = possibleRays.iterator(); iterator.hasNext();) {
	// CellW ray = iterator.next();
	// BoardW aTest = new BoardW(field);
	// int nbShot = aTest.shootRay(ray);
	// if (nbShot > bestShot) {
	// bestShot = nbShot;
	// bestRay = ray;
	// oneFound = true;
	// } else if (nbShot == 0) {
	// // remove when no mirror on the path
	// iterator.remove();
	// }
	// // if (oneFound && iterator.hasNext()) {
	// // iterator.next();
	// // }
	// }
	// return bestRay;
	// }

	private List<CellW> getBestRays(Collection<CellW> possibleRays, BoardW field, int nbTurns) {
		List<CellW> bestRays = null;
		long timeSinceStart = System.currentTimeMillis() - startTime;
		boolean try2ndRay = (((timeSinceStart < MAX_TIME_1) || possibleRays.size() < 180) && (timeSinceStart < MAX_TIME_2))
				|| (field.nbMirrors < 11);
		// log("getBestRays " + field.nbMirrors + " " + try2ndRay + " possibleRays.size()=" + possibleRays.size());
		int bestShot = 0;
		for (Iterator<CellW> iterator = possibleRays.iterator(); iterator.hasNext();) {
			// List<CellW> testedRays = new ArrayList<FragileMirrors.CellW>();
			CellW ray = iterator.next();
			// testedRays.add(ray);
			BoardW aTest = new BoardW(field);
			int nbShot = aTest.shootRay(ray);
			if (nbShot == 0) {
				// remove when no mirror on the path
				iterator.remove();
			} else {
				// 2nd ray
				if (try2ndRay) {
					for (Iterator<CellW> it2 = possibleRays.iterator(); it2.hasNext();) {
						CellW ray2 = it2.next();
						BoardW aTest2 = new BoardW(aTest);
						int nbShot2 = aTest2.shootRay(ray2);
						if (nbShot2 > 0) {
							int curNbShots = nbShot + nbShot2;
							if (curNbShots > bestShot) {
								bestRays = new ArrayList<CopyOfFragileMirrors.CellW>(2);
								bestShot = curNbShots;
								bestRays.add(ray);
								bestRays.add(ray2);
							}
						}
					}
				} else {
					int curNbShots = nbShot;
					if (curNbShots > bestShot) {
						bestRays = new ArrayList<CopyOfFragileMirrors.CellW>(1);
						bestShot = curNbShots;
						bestRays.add(ray);
					}
				}
				if (bestRays == null) {
					bestRays = new ArrayList<CopyOfFragileMirrors.CellW>(1);
					bestRays.add(ray);
				}
			}
			// if (oneFound && iterator.hasNext()) {
			// iterator.next();
			// }
		}
		return bestRays;
	}

	private Collection<CellW> getPossibleRays(int boardSize) {
		Collection<CellW> lstRays = new ArrayList<CopyOfFragileMirrors.CellW>();
		for (int i = 0; i < boardSize; i++) {
			CellW ray = new CellW(-1, i);
			lstRays.add(ray);
			lstRays.add(new CellW(boardSize, i));
			lstRays.add(new CellW(i, -1));
			lstRays.add(new CellW(i, boardSize));
		}
		return lstRays;
	}

	private void log(String string) {
		System.out.println(string);
	}

	class CellW {
		int r, c;

		public CellW(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	class BoardW {
		private static final byte LEFT = 1;
		private static final byte RIGHT = 2;
		private static final byte SPACE = 0;
		final int[] DR = new int[] { -1, 0, 1, 0 };
		final int[] DC = new int[] { 0, 1, 0, -1 };

		final int[] LL = new int[] { 1, 0, 3, 2 };
		final int[] RR = new int[] { 3, 2, 1, 0 };

		int N, nbMirrors;
		byte[][] what;

		public BoardW(String[] board) {
			this.N = board.length;
			this.nbMirrors = N * N;
			this.what = new byte[N][];
			for (int i = 0; i < N; i++) {
				// this.what[i] = board[i].toCharArray();
				byte[] line = new byte[N];
				this.what[i] = line;
				for (int j = 0; j < N; j++) {
					if (board[i].charAt(j) == 'L') {
						line[j] = LEFT;
					} else {
						line[j] = RIGHT;
					}
				}

			}
		}

		public void shootRay(List<CellW> curRays) {
			for (CellW ray : curRays) {
				shootRay(ray);
			}
		}

		public BoardW(BoardW tpl) {
			this.N = tpl.N;
			this.nbMirrors = tpl.nbMirrors;
			this.what = tpl.what.clone();
			// System.arraycopy(tpl.what, 0, this.what, 0, tpl.what.length);
			for (int i = 0; i < tpl.what.length; i++) {
				this.what[i] = tpl.what[i].clone();
			}
		}

		int shootRay(CellW ray) {
			int r = ray.r, c = ray.c;
			if (r == -1 && c >= 0 && c < N) {
				return shootRay(r, c, 2);
			} else if (r == N && c >= 0 && c < N) {
				return shootRay(r, c, 0);
			} else if (c == -1 && r >= 0 && r < N) {
				return shootRay(r, c, 1);
			} else if (c == N && r >= 0 && r < N) {
				return shootRay(r, c, 3);
			} else {
				System.err.println("in ERROR: ray " + " (0-based) starts at an invalid point (row " + r + ", column " + c + ").");
				return -1;
			}
		}

		int shootRay(int r, int c, int d) {
			int curR = r;
			int curC = c;
			int curD = d;

			int nbShot = 0;
			List<CellW> res = new ArrayList<CellW>();
			res.add(new CellW(curR, curC));
			curR += DR[curD];
			curC += DC[curD];

			while (curR >= 0 && curR < N && curC >= 0 && curC < N) {
				// if (what[curR][curC] == LEFT || what[curR][curC] == RIGHT) {
				if (what[curR][curC] != SPACE) {
					res.add(new CellW(curR, curC));
					curD = (what[curR][curC] == LEFT ? LL[curD] : RR[curD]);
					// what[curR][curC] = (what[curR][curC] == 'L' ? 'l' : 'r');
					what[curR][curC] = SPACE;
					nbMirrors--;
					nbShot++;
				}
				curR += DR[curD];
				curC += DC[curD];
			}

			res.add(new CellW(curR, curC));
			return nbShot;
		}

	}

}
